package day_2022_9_to_12.Day;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author haomin
 * @date 2022/10/26 17:00
 **/
public class Day54_1_Num862_ShortestSubarray {
    class Solution {
        public int shortestSubarray(int[] nums, int k) {
            int ans = Integer.MAX_VALUE;
            Queue<long[]> q = new PriorityQueue<>((a, b) -> a[0] < b[0] ? -1 : 1);
            q.offer(new long[]{0, -1});
            long sum = 0, target = 0;
            for(int i = 0; i < nums.length; ++i){
                sum += nums[i];
                target = sum - k;
                // 一个的前缀和小于当前的前缀和，那么已经就更新距离
                while(!q.isEmpty() && q.peek()[0] <= target)
                    ans = Math.min(ans, i - (int)q.poll()[1]);
                q.offer(new long[]{sum, i});
            }
            return ans <= nums.length ? ans : -1;
        }
    }
}